package com.hdu.other.dp.three;

public class lc2435 {
    class Solution {

        int MOD = 1000000007;

        public int numberOfPaths(int[][] grid, int k) {
            int m = grid.length;
            int n = grid[0].length;
            int[][][] dp = new int[m][n][k];
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    for (int l = 0; l < k; l++)
                    {
                        dp[i][j][l] = -1;
                    }
                }
            }
            return f(grid, m, n, 0, 0, 0, k, dp);
        }

        int f(int[][] grid, int m, int n, int row, int col, int r, int k, int[][][] dp)
        {
            if (row >= m || col >= n)
            {
                return 0;
            }
            if (row == m - 1 && col == n - 1)
            {
                if (grid[row][col] % k == r)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            if (dp[row][col][r] != -1)
            {
                return dp[row][col][r];
            }
            int curMod = grid[row][col] % k;
            // curMod = 5
            // r = 7
            // need = 7 - 5 = 2
            int need = 0;
            if (r >= curMod)
            {
                need = r - curMod;
            }
            else
            {
                // curMod = 4
                // r = 5
                // k = 7
                // (4 + x) % 7 = 5
                // x = 8
                need = k + r - curMod;
            }
            int ans = f(grid, m, n, row + 1, col, need, k, dp);
            ans = (ans + f(grid, m, n, row, col + 1, need, k, dp)) % MOD;
            return dp[row][col][r] = ans;
        }
    }
}
